package flowgraph;

import graph.Node;
import graph.NodeList;

import java.util.HashMap;
import java.util.Set;

import temp.Label;
import temp.Temp;
import temp.TempList;
import util.List;
import assem.Instr;
import assem.LABEL;
import assem.MOVE;

public class AssemFlowGraph extends FlowGraph<Instr> {

	public HashMap<Node<Instr>, TempList> liveIn;
	public HashMap<Node<Instr>, TempList> liveOut;
	public List<List<Instr>> instrs;

	// private final List<Node> nodeInst;

	public AssemFlowGraph(List<List<Instr>> blocks) {
		super();
		instrs = blocks;
		liveIn = new HashMap<Node<Instr>, TempList>();
		liveOut = new HashMap<Node<Instr>, TempList>();
		// nodeInst = new ArrayList<Node<E>>();

		// para cada bloco basico
		for (List<List<Instr>> lb = blocks; lb != null; lb = lb.tail) {

			// inicia com primeira instrucao do bloco basico
			Node<Instr> from;
			if ((from = contains(lb.head.head)) == null) {
				from = newNode(lb.head.head);
			}
			Node<Instr> to;

			for (List<Instr> l = lb.head.tail; l != null; l = l.tail) {
				// insere no com instrucao no grafo, caso nao exista
				if ((to = contains(l.head)) == null) {
					to = newNode(l.head);
				}

				addEdge(from, to);

				/*
				 * / jumps ou cjumps if (to.value.jumps != null) { addEdgeJumps(to, to.value.jumps.head, blocks); }
				 */
				from = to;
			}
		}
	}

	// calcula o Live In e Live Out
	public void computeLiveness() throws Exception {
		NodeList<Node<Instr>> list = mynodes;
		HashMap<Node<Instr>, TempList> liveInLine = new HashMap<Node<Instr>, TempList>();
		HashMap<Node<Instr>, TempList> liveOutLine = new HashMap<Node<Instr>, TempList>();
		for (int i = 0; i < list.size(); i++) {
			liveIn.put(list.head, new TempList(null, null));
			liveInLine.put(list.head, new TempList(null, null));
			liveOut.put(list.head, new TempList(null, null));
			liveOutLine.put(list.head, new TempList(null, null));
			list = list.tail;
			i = 0;
		}

		list = mynodes;

		do {
			for (int i = 0; i < list.size(); i++) {
				TempList tempInLine = liveIn.get(list.head);
				liveInLine.put(list.head, tempInLine);

				TempList tempOutLine = liveOut.get(list.head);
				liveOutLine.put(list.head, tempOutLine);

				buildLiveIn(list.head);
				buildLiveOut(list.head);

				list = list.tail;
				i = 0;
			}
		} while (compareInOut(liveInLine, liveOutLine));

	}

	private void buildLiveOut(Node<Instr> node) {
		liveOut.put(node, new TempList(null, null));
		for (NodeList<Node<Instr>> suc = node.succ(); suc != null; suc = suc.tail) {

			for (int i = liveIn.get(suc.head).size() - 1; i >= 0; i--) {
				// liveOut.get(node).add(liveIn.get(suc.head).get(i));
			}
		}
	}

	private void buildLiveIn(Node<Instr> node) {

		liveIn.put(node, new TempList(null, null));
		for (List<Temp> listTemp = use(node); listTemp != null; listTemp = listTemp.tail) {
			liveIn.get(node).head = listTemp.head;
		}
		for (int i = liveOut.get(node).size() - 1; i >= 0; i--) {
			Temp t = liveOut.get(node).head;
			// if (!isDef(t, node) && !liveIn.get(node).contains(t)) {
			// liveIn.get(node).add(t);
			// }
		}
	}

	// verifica se in'[n]=in[n] e out'[n]=out[n] para todo n
	private boolean compareInOut(HashMap<Node<Instr>, TempList> liveInLine, HashMap<Node<Instr>, TempList> liveOutLine) {
		boolean allEqualIn = true;
		Set<Node<Instr>> setLinesIn = liveInLine.keySet();

		for (Node<Instr> node : setLinesIn) {
			TempList tempsLine = liveInLine.get(node);
			allEqualIn = true;
			TempList temps = liveIn.get(node);
			if (temps != null && tempsLine != null && !temps.head.equals(tempsLine.head)) {
				allEqualIn = false;
			}
			if (!allEqualIn) {
				break;
			}
			while (tempsLine.tail != null) {
				tempsLine = tempsLine.tail;
				temps = temps.tail;
				if (temps != null && tempsLine != null && !temps.head.equals(tempsLine.head)) {
					allEqualIn = false;
				}
				if (!allEqualIn) {
					break;
				}
			}
			if (!allEqualIn) {
				break;
			}
		}

		boolean allEqualOut = true;
		Set<Node<Instr>> setLinesOut = liveOutLine.keySet();

		for (Node<Instr> node : setLinesOut) {
			TempList tempsLine = liveOutLine.get(node);
			allEqualOut = true;
			TempList temps = liveOut.get(node);
			if (temps != null && tempsLine != null && !temps.head.equals(tempsLine.head)) {
				allEqualOut = false;
			}
			if (!allEqualOut) {
				break;
			}
			while (tempsLine.tail != null) {
				tempsLine = tempsLine.tail;
				temps = temps.tail;
				if (temps != null && tempsLine != null && !temps.head.equals(tempsLine.head)) {
					allEqualOut = false;
				}
				if (!allEqualOut) {
					break;
				}
			}
			if (!allEqualOut) {
				break;
			}
		}
		return (allEqualIn && allEqualOut);
	}

	private boolean isDef(Temp temp, Node<Instr> node) {
		for (List<Temp> def = def(node); def != null; def = def.tail) {
			if (def.head.equals(temp)) {
				return true;
			}
		}
		return false;
	}

	private void addEdgeJumps(Node<Instr> from, Label label, List<List<Instr>> blocks) {
		Node<Instr> n = null;

		// verifica se aresta ja existe
		for (NodeList<Node<Instr>> nl = from.adj(); nl != null; nl = nl.tail) {
			if (nl.head.value instanceof LABEL &&
									((LABEL) nl.head.value).label.toString().equals(label.toString())) {
				return;
			}
		}

		// verifica se o no referente a label ja existe no grafo e a tribui a n caso exista
		for (NodeList<Node<Instr>> nl = mynodes; nl != null; nl = nl.tail) {
			if (nl.head.value instanceof LABEL &&
									((LABEL) nl.head.value).label.toString().equals(label.toString())) {
				n = nl.head;
			}
		}

		// caso o no nao exista, cria o no
		if (n == null) {
			for (List<List<Instr>> lb = blocks; lb != null; lb = lb.tail) {
				for (List<Instr> lt = lb.head; lt != null; lt = lt.tail) {
					if (lt.head instanceof LABEL &&
													((LABEL) lt.head).label.toString().equals(label.toString())) {
						System.out.println("achou");
						n = newNode(lt.head);
						addEdge(from, n);
						return;
					}
				}
			}
		}
		addEdge(from, n);
	}

	@Override
	public List<Temp> def(Node<Instr> node) {
		return node.value.def;
	}

	@Override
	public boolean isMove(Node<Instr> node) {
		return (node.value instanceof MOVE);
	}

	@Override
	public List<Temp> use(Node<Instr> node) {
		return node.value.use;
	}

}
